/*
 * CopyRight(C) Kenbin
 */

#ifndef LWS_WORDGRAPH_INCLUDED
#define LWS_WORDGRAPH_INCLUDED

#include <vector>
#include <iostream>

using namespace std;

/*Comment#
   整个分词可以分为三个阶段:
   1、词语粗切分
   2、切分排歧与未登录词识别
   3、词性标注

   词语粗切分又可以分为三个步骤:
   1、原子切分
   2、找出原子之间所有可能的组词方案(全切分)
   *3、N-最短路径求解

   所谓N-最短路径就是最少路径和全路径的折中,保留前N长度的路径.

   1、基于N-最短路径的非统计粗分模型

   N-最短路径方法的基本思想是根据词典,找出字串中所有可能的词构造词图
   (一种有向无环图),每个词对应图中的一条有向边,并赋给相应的边长(权值)
   .针对这个词图,N-最短路径求解就是在起点到终点的所有路径中,求出长度
   值按严格升序排列依次为第1、第2、...、第N的路径集合作为相应的粗分
   结果集.如果两条或两条以上路径长度相等,那么他们的长度并列第i,都要
   列入粗分结果集,最后的粗分结果集大小>=N.

   设待分字串C=c1c2..cn,其中ci为单个的字,n为串的长度,建立一个节点数
   为n+1的切分有向无环图,各节点编号依次为v0,v1,..,vn.通过以下方法建
   立词图所有可能的词弧(边):
   (1)相邻节点vk-1,vk之间建立有向边<vk-1,vk>,边的长度为lk,边对应的
      词默认为ck(k=1,2,..,n)
   (2)若w=cici+1..cj是一个词,则节点vi-1,vj之间建立有向边<vi-1,vj>,
      边的长度为lw,边对应的词为w

   N-最短路径的求解就是求v0到vn的N-最短路径集合.可以采用贪心方法,我们
   使用的算法是基于Dijkstra的一种简单扩展,改进的地方在于:每个节点处记
   录N个最短路径值,并记录相应路径上当前节点的前驱.如果同一长度对应多
   条路径,必须同时记录这些路径上当前节点的前驱.最后通过回溯可求出v0到
   vn的N-最短路径集合.

   以3-最短路径方法(Dijkstra)为例.

   词图如下,边长都为1:
                           的确[1]             实在[1]
                       --------------     --------------------
                      /              \   /                    \
       他[1]  说[1]  / 的[1]   确[1]  \|/ 实[1]   在[1]   理[1]\|
   (0)---->(1)---->(2)---->(3)------>(4)------>(5)---->(6)---->(7)
                            \                 /|\              /|
                             \    确实[1]    /   \   在理[1]  /
                              ---------------     ------------

   以下是节点记录,前驱记录了(节点号,编号)
   table(0)
   ----------------------
   | 编号 | 长度 | 前驱 |
   ----------------------
   | 1    | 0    | NULL |
   ----------------------<---| 0
   table(1)                  |
   ----------------------    |
   | 编号 | 长度 | 前驱 |    |
   ----------------------    |
   | 1    | 1    |(0,1) |--->|
   ----------------------<---| 1
   table(2)                  |
   ----------------------    |
   | 编号 | 长度 | 前驱 |    |
   ----------------------    |
   | 1    | 2    |(1,1) |--->|
   ----------------------<---| 2
   table(3)                  |
   ----------------------    |
   | 编号 | 长度 | 前驱 |    |
   ----------------------    |
   | 1    | 3    |(2,1) |--->|
   ----------------------<---| 3
   table(4)                  |
   ----------------------    |
   | 编号 | 长度 | 前驱 |    |
   ----------------------    |
   | 1    | 3    |(2,1) |    |
   ----------------------    |
   | 2    | 4    |(3,1) |    |
   ----------------------    |
   table(5)                  |
   ----------------------    |
   | 编号 | 长度 | 前驱 |    |
   ----------------------    |
   | 1    | 4    |(3,1) |--->|
   |      |      |(4,1) |    |
   ----------------------<---| 5
   | 2    | 5    |(4,2) |    |
   ----------------------    |
   table(6)                  |
   ----------------------    |
   | 编号 | 长度 | 前驱 |    |
   ----------------------    |
   | 1    | 4    |(4,1) |    |
   ----------------------    |
   | 2    | 5    |(4,2) |    |
   |      |      |(5,1) |    |
   ----------------------    |
   | 3    | 6    |(5,2) |    |
   ----------------------    |
   table(7)                  |
   ----------------------    |
   | 编号 | 长度 | 前驱 |    |
   ----------------------    |
   | 1    | 5    |(5,1) |--->| 7
   |      |      |(6,1) |
   ----------------------
   | 2    | 6    |(5,2) |
   |      |      |(6,2) |
   ----------------------
   | 3    | 7    |(6,3) |
   ----------------------
   现在从这些记录回溯第1条最短路径.由最后一个节点7记录中找出最短长度对应的
   第一个前驱为(5,1),并沿着前驱继续查节点5的编号1的记录,得前驱(3,1),依此类
   推得前驱(2,1)(1,1)(0,1),得到的切分为:0 1 2 3 5 7,即: 他/说/的/确实/在理.

   在非统计模型构建词图的过程中,给每个词对应的边长赋值为1.随着字串长度n和
   最短路径数N的增大,长度相同的路径数急剧增加,同时粗切分结果数量必然上升,
   例如,N=2时,句子"江泽民在北京人民大会堂会见参加全国法院工作会议和全国法
   院系统打击经济犯罪先进集体表彰大会代表时要求大家要充分认识打击经济犯罪
   工作的艰巨性和长期性"的粗切分结果居然有138种之多,大量的切分结果对后期的
   处理,以及整体性能的提高是非常不利的.

   *2、基于N-最短路径的统计粗分模型

   假设字串为C=c1c2..cn,要求的词串为W=w1w2..wm.求使得概率P(W|C)的值是最大
   的N个W,采用一元统计模型,即只引入词频并假定词与词之间是相互独立.我们引入
   词wi的词频信息P(wi),对模型进行改进,得到一个基于N-最短路径的一元统计模型.

   由贝叶斯定理:P(W|C)=P(W)P(C|W)/P(C),其中,P(C)是字串概率,是一个常数,不必
   考虑.从词串恢复到字串的概率P(C|W)=1(只有唯一的一种方式,因为字串只有一个).

   问题就转化为确定P(W)最大的N种切分结果集合.

   W=w1w2..wm是字串C=c1c2..cn的一种切分结果.wi是一个词,P(wi)表示wi的出现概
   率.在大规模语料库训练的基础上,根据大数定理:在大样本统计的前提下,样本的
   频率接近于其概率值.所以P(wi)的极大似然估计值等于词频有: 
   P(wi) = ki / (k1 + k2 + .. + km),ki为wi在训练样本中出现的次数

   对于一元统计模型,词与词之间是独立的,则W的联合概率
   P(W)=P(w1)*P(w2)*..*P(wm),设K=k1+k2+..+km,则:
   P(W)=(k1/K)*(k2/K)*..*(km/K),令P*(W)=-lnP(W),则: 
   P*(W) = -lnP(w1)-lnP(w2)-..-lnP(wm) 
   = -ln(k1/K)-ln(k2/K)-..-ln(km/K) = m*ln(K)-ln(k1)-ln(k2)-..-ln(km)

   那么就把求P(W)的极大值问题转化为求P*(W)的极小值问题.适当修改切分有向无环
   图边长(加1是为了数据平滑处理):
   (1)*<vk-1,vk>的长度值lk=-ln(0+1),(k=1,2,..,n)
   (2)*w=cici+1..cj对应的有向边为<vi-1,vj>,其长度值lw=ln(K+m)-ln(ki+1)

   根据修改边长后的词图,直接使用上面的算法,就可以实现问题的最终求解.
*/

namespace LWS {

    struct GraphNode
    {
	int pre_node;
	int word_id;
	float word_prob;
    };

    class CWordGraph
    {
	public:
	    void Init(int total_node);
	    void AddWord(int first_CHAR_pos, int last_CHAR_pos, int word_id, float word_prob);
	    void GenerateBestPath();
	    void Print();

	    vector<vector<GraphNode> > m_word_graph;
	    vector<int> m_best_node_path;
	    vector<int> m_best_wordid_path;
    };

};

#endif
